package com.bigshen.algorithm.bStack.solution03MaxsumRange;

import java.util.Stack;

/**
 *
 * 区间最小值*(区间和)   取最大值
 *
 *   区间： 5,2,3,4,1
 *   [0-0]  5*5=25
 *   [0-1]  2*(5+2)=14
 *
 *   第一种方式：
 *      O(N^2)，两层for循环遍历 for(i=0-size) { for(j=i-size) }
 *
 *   优化点 :
 *      1. 不需要每次都计算区间和，存在重复计算，是否可以复用？
 *              ====》 第一次遍历，计算 0到每个下标区间的 sum
 *      2. 当前元素x，后续元素比x大时，不需要计算区间和，因为结果值=x*(x + 后续比x大的值)
 *          针对 2、3、4，不用计算 2*2,2*(2+3)，而是可以直接计算2*(2+3+4)，因为能继续相加的值肯定比之前的大
 *             遇到下一个元素比当前元素小的，那么当前元素就有权利计算一次了。
 *          ======》  考虑采用栈 Stack，当前最小值x放入栈，后续比x小的话也入栈，比x大则出栈 有权利进行计算
 */
public class Solution03 {

    // 5.2. 3. 4. 1
    // 5.7.10.14.15

    // 1.2.3.4.5
    public int getRangeSumMax(int[] array) {

        if (null == array || array.length == 0) {
            return 0;
        }

        // 提前计算区间和
        int[] sums = new int[array.length+1];
        for (int i = 0; i < array.length; i++) {
            sums[i+1] = sums[i] + array[i];
        }

        // 找出每个区间最小值，及其区间左右下标
        Stack<Integer> stack = new Stack<>();
        Integer max = null;
        for (int i = 0; i < array.length; i++) {
            int element = array[i];

            while (!stack.isEmpty() && array[stack.peek()] > element) {
                // 下一个值比当前值小，出栈计算 (当前栈内的值可以计算一次区间和乘积)
                int index = stack.pop();
                // 计算左区间，如果左侧没值，从0开始累加
                int left = stack.isEmpty() ? 0 : index;
                int right = i;
                int currentMax = array[index] * (sums[right] - sums[left]);
                max = (max == null || max < currentMax) ? currentMax : max;
                System.out.println(String.format("正向遍历至下标 %s 处值为 %s，发现当前值比前一值 %s 小->前一值出栈计算，进行计算区间乘积： %s*%s = %s",
                        i, element, array[index], array[index], sums[right] - sums[left], currentMax));

            }
            stack.push(i);

        }

        while (!stack.isEmpty()) {
            int index = stack.pop();
            // 计算左区间，如果左侧没值，从0开始累加
            int left = stack.isEmpty() ? 0 : index;
            int right = array.length;
            int currentMax = array[left] * (sums[right] - sums[left]);
            max = (max == null || max < currentMax) ? currentMax : max;
            System.out.println(String.format("反向遍历，当前值 %s， 区间和 %s， 区间乘积 %s", array[left], sums[right] - sums[left], currentMax));
        }
        return max;
    }

    public static void main(String[] args) {

//        int[] array = {5,4,3,2,1};
        int[] array = {1,2,3,4,5};
//        int[] array = {5,2,3,4,1};
        System.out.println(new Solution03().getRangeSumMax(array));

    }

}
